#include <array>
#include <functional>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

class Solution {
  public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty()) return false;
        std::vector<std::vector<bool>> flag(board.size(), std::vector<bool>(board[0].size(), true));
        std::function<bool(int, int, int)> helper;
        helper = [&](int x, int y, int i) {
            // std::cout << board[x][y] << word[i] << '\n';
            if (board[x][y] != word[i] or (not flag[x][y])) return false;
            if (i == word.size() - 1) return true;
            flag[x][y] = false;

            // 一个技巧是可以设置一个方向数组{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
            if (x + 1 < board.size() and helper(x + 1, y, i + 1)) return true;
            if (y + 1 < board[0].size() and helper(x, y + 1, i + 1)) return true;
            if (x - 1 >= 0 and helper(x - 1, y, i + 1)) return true;
            if (y - 1 >= 0 and helper(x, y - 1, i + 1)) return true;

            flag[x][y] = true;
            return false;
        };
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                if (helper(i, j, 0)) return true;
            }
        }
        return false;
    }
};

int main() {
    std::vector<std::vector<char>> board{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
    std::string word{"SFC"};
    Solution s;
    s.exist(board, word);
}
